package main

import "fmt"

func main() {
	root := &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 3,
			},
			Right: &TreeNode{
				Val: 4,
			},
		},
		Right: &TreeNode{
			Val: 2,
			Left: &TreeNode{
				Val: 4,
			},
			Right: &TreeNode{
				Val: 3,
			},
		},
	}

	// root := &TreeNode{
	// 	Val: 1,
	// 	Left: &TreeNode{
	// 		Val: 2,
	// 		Right: &TreeNode{
	// 			Val: 3,
	// 		},
	// 	},
	// 	Right: &TreeNode{
	// 		Val: 2,
	// 		Right: &TreeNode{
	// 			Val: 3,
	// 		},
	// 	},
	// }
	fmt.Println(isSymmetric(root))
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
//构造一个满二叉树，使用bfs遍历，每一层都是对称的即可 (执行超时)
// func isSymmetric(root *TreeNode) bool {
// 	if root == nil {
// 		return false
// 	}

// 	q := []*TreeNode{root}
// 	hasValue := true
// 	for len(q) > 0 && hasValue {
// 		size := len(q)
// 		if len(q) >= 2 {
// 			// 检查数组是否对称
// 			p1, p2 := 0, len(q)-1
// 			for p1 < p2 {
// 				if q[p1] == nil && q[p2] == nil {
// 					continue
// 				}
// 				if q[p1] == nil {
// 					return false
// 				}
// 				if q[p2] == nil {
// 					return false
// 				}
// 				if q[p1].Val != q[p2].Val {
// 					return false
// 				}
// 				p1++
// 				p2--
// 			}
// 		}

// 		hasValue = false
// 		for i := 0; i < size; i++ {
// 			n := q[0]
// 			q = q[1:]
// 			if n.Left != nil {
// 				hasValue = true
// 				q = append(q, n.Left)
// 			} else {
// 				q = append(q, nil)
// 			}

// 			if n.Right != nil {
// 				hasValue = true
// 				q = append(q, n.Right)
// 			} else {
// 				q = append(q, nil)
// 			}
// 		}

// 		if !hasValue {
// 			return true
// 		}
// 	}

// 	return true
// }

func isSymmetric(root *TreeNode) bool {
	// return check_dec(root.Left, root.Right)
	return check(root.Left, root.Right)
}

func check_dec(p1 *TreeNode, p2 *TreeNode) bool {
	if p1 == nil && p2 == nil {
		return true
	}

	if p1 != nil && p2 == nil {
		return false
	}

	if p1 == nil && p2 != nil {
		return false
	}

	if p1 == nil || p2 == nil {
		return false
	}

	return p1.Val == p2.Val && check_dec(p1.Left, p2.Right) && check_dec(p1.Right, p2.Left)
}

func check(p1 *TreeNode, p2 *TreeNode) bool {
	q := []*TreeNode{p1, p2}
	for len(q) > 0 {
		n1 := q[len(q)-1]
		q = q[:len(q)-1]
		n2 := q[len(q)-1]
		q = q[:len(q)-1]

		if n1 == nil && n2 == nil {
			return true
		}

		if n1 == nil || n2 == nil {
			return false
		}

		if n1.Val != n2.Val {
			return false
		}

		if n1.Left != nil || n2.Right != nil {
			q = append(q, n1.Left)
			q = append(q, n2.Right)
		}  

		if n1.Right != nil || n2.Left != nil{
			q = append(q, n1.Right)
			q = append(q, n2.Left)
		}

	}

	return true
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
